图网络如何助力城市大脑：跨时空大尺度网约车流量预测
据 Uber 统计，2018年，全年的网约车使用次数达180亿次，超过全球人口的两倍。准确的网约车订单预测，能够更好的调度车辆，提高车辆的利用率，减少等待时间，从而缓解交通拥堵，具有重要的经济和社会意义。近年来大火的图神经网络 GNN 相当于提供了一种新的建模和解决时空数据预测的手段。
ST-MGCN 是滴滴出行 AI Lab 发表于 AAAI 2019 的一种基于时空多图卷积网络的网约车需求量预测模型。区域级需求预测是网约车服务的关键技术。准确的网约车需求量预测可以指导车辆的调度，提高车辆的利用率，减少等待时间，以及缓解交通拥堵。区域之间所存在复杂的时空依赖关系使得这个问题具有很大挑战。已有方法主要关注于建模相邻区域在空间上的欧式相关性（Euclidean correlations），而作者发现距离较远区域之间的非欧相关性也对预测至关重要。
论文题目：
Spatiotemporal Multi-Graph Convolution Network for Ride-hailing Demand Forecasting
论文地址：
http://www-scf.usc.edu/~yaguang/papers/
aaai19_multi_graph_convolution.pdf
本文提出了时空多图卷机网络 spatiotemporal multi-graph convolution network (ST-MGCN)，一个新的用于网约车需求预测的深度学习模型。作者首先将区域间的非欧相关性建模到多个图，然后用多图卷积（multi-graph convolution）来建模其相关性。用全局上下文信息（global contextual information）来建模时序信息，并进一步提出了上下文门控循环神经网络模型（contextual gated recurrent neural network），给历史数据分配权重。在两个数据集上表现强于已有算法的 10% 以上。
论文背景
据 Uber 统计，2018年，全年的网约车使用次数达180亿次，超过全球人口的两倍。准确的网约车订单预测，能够更好的调度车辆，提高车辆的利用率，缓解交通拥堵，具有重要的经济和社会意义。
网约车需求量预测问题可以通过其数据建模方式来理解。以1小时为时间单位，1km*1km 的网格为空间单位，某城市某个小时订单量可以用如下所示的2d格点图片来表示，每个格点的数值是在该时间段内该区域所产生的滴滴打车的订单数的总和。那么所谓网约车需求量预测，就是已知过去几个小时每个格点的订单数，预测未来的订单数。
基于 grid 建模数据的示意图
实际上，直接做网约车需求量预测的文章并不多，但这个问题可以归结为交通流预测，并且本文的对比算法也是交通流预测模型，在同一网约车数据集上的表现。此外，交通流预测属于城市计算问题（urban computing）Yu Zheng. 2014. Urban Computing Concepts, Methodologies, and Applications。这个概念由当时还在微软亚洲研究院的郑宇提出。与我们生活息息相关的很多问题都可以归结为城市计算问题。比如车辆调度问题，输电网优化，物流及供应链管理，雾霾预测等。它们的特点是同时具有时间和空间两个维度的信息。近年来大火的图神经网络 GNN 相当于提供了一种新的建模和解决时空数据预测的手段。
问题定义
本文要解决的问题是，如何能够更好的建模多个区域之间所存在的非欧且多模态的时间和空间相关性，以实现高准确率的网约车需求量预测。
问题的数学表述如下，输入连续 T 个时刻的格点集合 X（格点的值为订单数），输出下一时刻的订单数，通过训练学习得到该映射函数 f。
这里的多模态可以理解为多重维度的关系。如下图所示，图中区域1和区域2在空间上是相邻关系，他们可能会有相似的约车量。区域1和区域3在功能上是相似的，可能在用车的 pattern 上存在比较高的相似性。区域4与区域1在同一条路旁边，同理，他们也会存在某种约车的相似性。
此外，订单数还与时间紧密相关，比如早晚高峰，节假日等，会对用车数产生比较大的影响，且会呈现某种周期性。所以，作者总结了这个问题所面临的两个挑战。空间上，需要学习区域间存在的多模态非欧相关性。时间上，需要学习复杂的多个时刻的时间依赖关系。
时空数据预测的相关工作可以分为两类：1. 将数据建模成为 2d image 上的格点，使用 CNN 的方法进行预测；2. 将数据建模到 graph 的节点上，基于图的方法进行预测。建模称为 2d image 的方法无法处理非欧数据（CNN 所处理的规整的网格是欧式空间）。假如就这个问题而言，我们建模为 1km*1km 的网格，那么整个城市不同区域使用的分辨率都是相同的，如果我们希望在市中心用更高的分辨率，郊区用更低的分辨率，或者加入某些兴趣点，这种方法是无法实现的。而现有基于 graph 的方法，虽然在区域建模上具有很高灵活性，但是无法建模上述区域间多模态的相关性。
算法框架
作者基于对网约车需求量预测问题的理解以及先验知识，设计了如下的算法框架。
主要分为三部分。
将每一帧的数据建模成为三张 graph。每张 graph 上的节点相同，即城市的网格化划分。连边通过如下图所示的规则进行构建。根据不同维度的相关性（邻域信息、功能相似度、交通连通性）确定节点之间的连边值。
时间维度的预测：将T个历史时间步的信息融合到一张图上。
空间维度的预测：将一个时刻的不同的相关性的图合成一个图。这就是论文题目中所说的多图卷积。
Contextual Gated Recurrent
Neural Network (CGRNN)
这是算法框架中的第二步，将 T个时间步的历史数据融合为一张图，这里所谓的 Contextual Gated 是指将历史数据每一帧通过图卷积网络进行数据融合，并且通过全局 pooling 得到该小时的全局信息。这个全局信息再与原来的 T个时间步的数据做点乘，得到了带权重的历史数据。然后迭代地输入到 RNN 中进行时间维度的信息融合，最终得到一张图。这里的 RNN 是权值共享的，也就是对于图上的每个顶点都过同一个 RNN，它们的所训练的是一套参数（工程上是可以实现的）。这样的好处有两点：1. 学习更加 general 的时序维度的汇聚方法，2. 减少模型复杂程度，使得更容易训练。
pooling 操作如下所示，将 t 时刻 graph 上所有节点的值都加起来，然后除以节点的个数。
这里需要注意的点是，每一帧数据做图卷积的方法是使用 k-ordered ChebNet。这个方法与我们熟知的图卷积网络 GCN 的区别是，GCN 可以简单地认为是 1-ordered ChebNet，只是汇聚一阶邻居。如文中给出的示意图所示。黑色是中心节点，黄色是 1阶邻居，红色是 2阶邻居。通过 k-ordered ChebConv，可以实现 k 阶领域的信息交互。使用 k 层的 GCN 堆叠也可以实现 k 阶邻域信息角度，但是随着层数增加，训练难度加大。所以，这可能是作者做模型选择的考虑点之一。
下面是相关的运算公式：
对 GCN 也不太熟悉的同学可以这样通俗的理解 GCN 的作用。每个 graph，都有对应的表示节点连接关系的邻接矩阵，还有数值在主对角线上，表示节点一阶邻居个数的度矩阵。拉普拉斯矩阵是通过邻接矩阵、度矩阵，用上面图中的公式计算得到的一个方阵。
在图卷积中，拉普拉斯矩阵中的元素，用来充当节点之间信息汇聚时，邻居节点的特征向量相加中前面对应的权重。下图是算法框架中第三步的内容（这两步都用到 k-ordered ChebConv）。其中不考虑多图的汇聚，花括号中的内容就是一个图上进行卷积的操作。第一个方阵就是拉普拉斯矩阵，第二个矩阵是这本卷积层的输入的邻居节点的特征向量（维度是 V*P，V 是节点个数，编号等同于拉普拉斯矩阵中节点编号，也就是节点在行向量的排序，P 是特征向量维度）。这两个矩阵进行矩阵乘法，得到的就是每个节点汇聚了其邻居节点特征的新的特征信息。这里的邻居节点根据算法的 k-ordered 所定义的 k 而不同，而范围不同，且会体现到拉普拉斯矩阵上。第三个矩阵 W 起到的作用等价于 MLP，做特征向量维度的变换。
感兴趣的同学可以阅读下面资料获取更详细的信息：GCN 作者 Kipf 的blog Convolutional Neural Networks on Graphs with Fast Localized Spectral Filtering，回顾频谱图卷积的经典⼯工作: 从ChebNet到GCN，拉普拉斯矩阵，
Multi-Graph Conv
算法的第三步所进行的是多图的信息汇聚。下图是以单个节点的视角来看这个算法的运行。首先，每个节点先各自通过 k-ordered ChebConv，然后在进行多图汇聚，汇聚操作的单位是节点。在这里是将前面分别建模了邻居信息、功能相似度、交通连通性的三个图进行汇聚。
下图是具体的多图汇聚的公式，括号内就是普通的 k阶 ChebConv，汇聚的方法可以是加和、平均、基于 attention 的汇聚等。
实验
模型基于滴滴打车在北京和上海两个城市的历史订单数据进行实验。对比了一些基本的时序预测（如果不考虑图上节点之间的空间相关性，可以看成时序预测问题）模型，基于 image 建模的算法，基于 graph 的算法等。均得到了 10% 的提升。并且进一步试验了去掉 multi-graph 中的某个图，以及替换时间维度信息的汇聚方法，均证明当前的模型是最好的。
总结
作者提到，接下来会将算法推广到其他的时空数据预测问题上，比如交通流、人流、雾霾预报等，以及提高模型的能力，以满足多个时间步的预测需求。
此外，笔者认为，基于该文章的多图数据融合机制，增加高精度的降水短临预报（例如，提供分钟级、街道级降水预报的彩云天气，http://caiyunapp.com/ ）可以显著提升订单数的预测准确性。
本文提到的 k-order ChebNet 和上次读书会分享的 GeniePath：自适应感受路径的图神经网络 GeniePath 复现代码 Github 链接，都是可以进行 k-hop 邻居信息汇聚的方法，可以简单地认为 GeniePath 是增加了 LSTM 的存储 cell 的 GCN，以实现文章提到的自适应感受野的目的。本文的代码复现，后续会发到的链接（https://github.com/shawnwang-tech/ST-MGCN-pytorch ）。感兴趣的读者可以 star 关注。
视频回顾
参考资料
• 作者个人主页：
http://www-scf.usc.edu/~yaguang
• 论文地址：
http://www-scf.usc.edu/~yaguang/papers
/aaai19_multi_graph_convolution.pdf
• slides：
http://www-scf.usc.edu/~yaguang/papers
/aaai19_multi_graph_convolution_slides.pdf
• poster：
http://www-scf.usc.edu/~yaguang/papers
/aaai19_stmgcn_poster.pdf
• echarts格点地图
• 郑宇：深度学习在时空数据中的应用
https://mp.weixin.qq.com/s/GakpFYtiNrVMNjPXUVjn1A
• Junbo Zhang, Yu Zheng, Dekang Qi. AAAI 2017. Deep Spatio-Temporal Residual Networks for Citywide Crowd Flows Prediction
https://arxiv.org/abs/1610.00081
• 回顾频谱图卷积的经典工作:
从ChebNet到GCN：
https://www.bilibili.com/read/mobile/2855698
作者：王硕
编辑：张爽
推荐阅读
Nature | 自动驾驶调度算法有望将出租车数量减少一半（内附论文原文）
共享汽车匹配算法如何导致司收入的巨大差异 | 网络科学论文速递12篇
集智俱乐部QQ群｜877391004
商务合作及投稿转载｜swarma@swarma.org
◆ ◆ ◆
搜索公众号：集智俱乐部
加入“没有围墙的研究所”
让苹果砸得更猛烈些吧！